COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	                          Math/CIS 280 exam answers
C00008 00003	****************
C00015 00004	**************
C00019 ENDMK
C⊗;
                          Math/CIS 280 exam answers

write the following functions or predicates 

dellst[u]         6 points
For the list u, dellst return a list of the atomic elements of u.
Examples:
	dellst[(A B C)] = (A B C)
	dellst[(A (B C) D (E))] = (A D)

Write dellst two ways: with and without a use of functional arguments.

dellst[u] <= 
	[null[u] → ()	
         atom[first[u]] → concat[first[u];dellst[rest[u]]]
         T → dellst[rest[u]]
        ]



vectoradd[u;v]    3 points
For lists u and v (assumed to be of equal length) this function this function returns
a list, each element of which is the sum of the corresponding elements in u and v. 
You may use plus[x;y] <= x+y; do with and without functional arguments.
Examples:
	vectoradd[(5 3);(2 -4)] = (7 -1)

vectoradd[x;y] <= mapbinary[x;y;function[plus]]
	
mapbinary[x;y;f] <= 
	[null[x] → ()
	 T → concat[f[first[x];first[y]];mapbinary[rest[x];rest[y] f]]
	]


allthesame[u]     3 points
For the  list u,  allthesame returns  T if  and only  if all  the elements  of u  are
identical. 

allthesame[u] <=
	[null[u] → T
	 T → alt1[first[u];rest[u]]
	]

alt1[x;l] <=
	[null[l] → T
	 eq[x;first[l]] → alt1[x;rest[l]]
	 T → NIL
	]

setdif[u;v]       3 points
For the lists, u and v, setdif returns a list consisting of all elements contained in
u and not contained in v. 
Examples:
	setdif[(5 4);()] = (5 4)
	setdif[(X 4 Y); (2 3 4)] = (X Y)
	setdif[(A B);(B C A D)] = ().

setdif[u;v] <=
	[null[u] → ()
	 member[first[u];v] → setdif[rest[u];v]
	 T → concat[first[u] setdif[rest[u];v]]
	]

*************
Modifying the evaluator:   10 points
We have been using λ-notation as a binding mechanism for call-by-value.  We have aslo
noticed that it would  be convenient to have arguments passed into a function body in
unevaluated form (special forms, for  example).  We propose  to add a new binder,  β,
which  will be  used  in contexts  like  the  λ-notation but  the  arguments are  NOT
evaluated before they are passed into the body of the β-expression. 

Show what modifications would have to be made to our current evaluation scheme.

For example: Given, foo <=λ[x]car[x]  evaluation of foo[cons[A;B]] would give A.
What would 
   baz <= β[[x;y]cons[x;y]] give as evaluation for baz[car[A];cdr[b]]?

HINT: This problem requires understanding the questions of representation.


Discussion:

Since all LISP expression evaluation is done by interpreting the Cambridge
Polish representation, "foo[cons[A;B]]" would be phrased as
(FOO (CONS (QUOTE A)(QUOTE B)). Similarly (BAZ(CAR (QUOTE A))(CDR B))
would be the call; thus (since cons is call-by-value) we would get
((CAR(QUOTE A)) . (CDR B))  as value of baz-expression.

We now have to modify the evaluation scheme. The key is to get hold of the
expression inside eval or value; BEFORE apply has a chance to evlaute
the argument list.

inside eval, something like:

is_β_expression[e] → apply [fn[e];args[e]; tbl]

and an "is_β[fn] →  eval[bdy[fn] newenv[args[fn]; eargs; tbl]]"

in the general case of LISP hackery, discovering whether or not 
is_β-expression is true or false is complicated. LISP can have computed functions,
as we will see.  is_β is easy: is this a rep of  β[[...] ...].

****************
A pattern matcher:    13 points
A pattern is an expression containing variables which may  take on "values" which are
subexpressions. For example, consider the expression
   e = (TIMES (PLUS 3 X) (PLUS 7 2) 3)
and the pattern
   p = (TIMES (PLUS VAR1 X) VAR2 VAR1).

This pattern, p, matches the  expression if VAR1 and VAR2 are bound to  3 and (PLUS 7 2)
respectively.    Define  a  function,  inst[e;p;m]  whose  value  is  a  table  of
variable-bindings (a simple symbol table)  which when substituted into the  argument,
p,  yields the  expression e.  The argument,  m, is  an initial  table of  previously
committed  substitutions. inst is to return NO if  the pattern does not match, and ()
if the pattern (modified by  the initial value of m) is identical  to the expression.
Thus  using the  above  examples of  p and  e,  inst[e;p;()] should  return something
representing  {<VAR1:3>, <VAR2:(PLUS  7  2)>}.   But  (again  using  p and  e  above)
inst[e;p; {<VAR1:4>}] returns NO.  As usual make the function as abstract as posible,
separating out  the representational  details to  subfunctions. In  dealing with  the
represntation, you may assume  whatever naming scheme you wish for  the VARs. You may
assume that no VARs occur in the expression, e. In fact, if VARs DO occur, you have a
another headache!  Those of you who are masochistic might examine that problem. 


yuck!!! what you did to this problem should be against the law.

inst[e;p;m] <= 
	[eq[m;NO] → NO;
	 is_var[p] → check_it[p;assoc[p;m];e;m]
	 atom[p] → [equal[p;e] → m; T → NO]
	 atom[e] → NO
	 T → inst[rest[e];rest[p]; inst[first[e];first[p];m] ] ]


Now, isn't that much milder than Brand X???

check_it[p;v;e;m] <=
	[null[v] → concat[mkent[p;e]m]
	 equal[val[v];e] → m]
	 T → NO ]


************
Write an algebraic simplifier:   13 points
As we saw in  the differentiation example (p. 39  - Stupor LISP) the results  of such
manipulation  in  symbolic   mathematics  can  lead  to  very  poor  representations.
Sophisticated algebraic simplifiers are a necessity.  Begin the construction  of such
a simplifier, keeping its structure as  separate as possible from the representation.
You  may restrict attention  to expressions involving variables,  integers, and sums,
products and powers  of such.  Show  your representation of the  simplification rules
and take care to allow easy addition of new rules. 

Your rules should include such as x+0=>x, x*0=>0, x↑0=>1,... .

Well, this problem IS a problem. Many people have spent many sleepless
nights worrying about simplification.

************
A quessing game:       5 points
what does this function do?

foo <= λ[[x] [atom[x] → x; T → cons[foo[car[x]];foo[cdr[x]]] ]

answer: not bloody much! Mathematically, its an identity function; computationally
(on MOST lisp machines) it copies its argument. The benefits of such trickery
will become apparent when we start talking about modification of list-structure.
************
a problem and a question of efficiency:      11 points
Let l be a list  of length n: (l1, l2, l3,  ln). Each li is also a list  of length m.
Write  a function, aargh[l] which  is to return  that first sequence  (l1j, l2j, lnj)
whose elements are not all equal. 
For example:
	aargh[((A B C)(A C E)(A B E))] = (B C B)
	aargh[((A B C D)(A B E (1)))] = (C E)

Try to make an efficient computation. Explain the difficulties involved.

discussion: if you liked inst, you'll love aargh:

aargh[l] <=
	[allempty[l] → T
	 allthesame[mapcar[function[first];l]] → aargh[mapcar[function[rest];l]]
	 T → mapcar[function[first];l]
	]

eat your heart out!!

allempty[l] <=
	[null[l] → T
	 null[first[l]] → allempty[rest[l]]
	 T → NIL ]

inefficency occurs in having to  recompute "mapcar[function[first];l]" when we
find desired column. 

*************
And still it comes: additions to the evalautor      10 points
Write modifications to the value[e;tbl] function  which will  handle sums of  arbitrary
length. Do it two ways: with and without functional arguments. 

DISCUSSION: do it inside apply --after evaluation of args.

apply[fn;eargs;tbl] <=

 .....
is_plus[fn] → plus_it[eargs]



plus_it[l] <= plus*[l;0]

plus*[l;n] <=
	[null[l] → n
	 T → plus*[rest[l]; plus[first[l];n]
	]
**************
equality on data structures         23 points
Recall that  a sequence (x1,  x2, x3, xn)  was defined as  having a  specific imposed
order: (A,  B) ≠ (B, A); and  two sequences are equal if  they are element-wise equal
and have the same length: (A, B, C) ≠ (A, B). 

A set {x1, x2,  x3, xn} on the other  hand, is defined as an  unordered collection of
elements; reptitions are not included:
    {1,2,A} = {A,2,1} = {A,2,A,1,1}

A data structure intermediate in complexity (between sets  and sequences) is a "bag".
A bag <x1, x2,  x3, xn>, has no imposed order, but may have repeated elements: 
<1, 2, 2> = <2, 1, 2> but does not equal <1, 2>. 

Notice that one  application of sequences is  the parameter-list to a  function call:
f[a1,a2, ...an].  The order of the ai's is important  and there can be repetitions (a
sequence).  FIRST QUESTION:  bags are a useful notation  for the parameter-list of  a
certain class of functions. what is this class ( 2 points). 

Pick representations for  each of these three  data structures. Write versions  of an
equality predicate which will implement the desired equality. 

equal_seq[(E,A,A,D,B,C);(A,B,D,E)] = NIL
equal_set[{E,A,A,D,B,C};{A,C,B,D,E}] = T
equal_bag[<E,A,D,A,C>;<A,C,A,D,E>] = T

points: 3 for sequences, 9 for sets, and 9 for bags.

discussion: should pick representation such that  we can distinguish between
types; and such that the recognizers are CHEAP!! 

eg (BAG e1 e2   en)   etc.

assuming recognizers strip off type information then

eq_seq[l;m] <=
	[null[l]→ [null[m]→T;T→NIL]
	 null[m]→ NIL
	 eq[first[l];first[m]] →eq_seq[rest[l]; rest[m]]
	 T → NIL]

The cheap way to handle sets and bags is to canonicalize them. That is
require a unique representation for equivalent sets or bags. (Bet
you wish you'd thought of that; --I wish you had too!!)
Then  <1,2,2> has the same representation as <2,1,2> etc. Similarly for
sets: {a,b,c} and {a,c,b} or {a,b,a,c,c} all have the same representation.